|
Van der Waerden's theorem states that for any positive integers ''r'' and ''k'' there exists a positive integer ''N'' such that if the integers are colored, each with one of ''r'' different colors, then there are at least ''k'' integers in arithmetic progression all of the same color. The smallest such ''N'' is the van der Waerden number ''W''(''r'',''k''). ==Tables of Van der Waerden numbers== There are two cases in which the van der Waerden number is easy to compute: first, ''W''(1,''k'')=''k'' for any integer ''k'', since one color produces only trivial colorings RRRRR...RRR (for the single color denoted R). Second, ''W''(''r'',2)=''r''+1, since we may construct a coloring that avoids arithmetic progressions of length 2 by using each color at most once, but once we use a color twice, a length 2 arithmetic progression is formed (e.g., for ''r''=3, the longest coloring we can get that avoids an arithmetic progression of length 2 is RGB). There are only seven other van der Waerden numbers that are known exactly. Bounds in this table taken from Rabung and Lotts except where otherwise noted. : Van der Waerden numbers with ''r'' ≥ 2 are bounded above by : as proved by Gowers. 2-color van der Waerden numbers are bounded below by : where ''p'' is prime, as proved by Berlekamp. One sometimes also writes ''w''(r; ''k''1, ''k''2, ..., ''k''''r'') to mean the smallest number ''w'' such that any coloring of the integers with ''r'' colors contains a progression of length ''k''i of color ''i'', for some ''i''. Such numbers are called ''off-diagonal van der Waerden numbers''. Thus ''W''(''r'', ''k'') = ''w''(r; ''k'', ''k'', ..., ''k''). Following is a list of some known van der Waerden numbers: Van der Waerden numbers are primitive recursive, as proved by Shelah; in fact he proved that they are (at most) on the fifth level of the Grzegorczyk hierarchy. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Van der Waerden number」の詳細全文を読む スポンサード リンク
|